package 力扣._100030_将石头分散到网格图的最少移动次数;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    //淦，有后效性，只能用动态规划
    public int minimumMoves(int[][] grid) {
        //这里的公共边相邻格子是指上下左右
        //BFS+贪心
        //得同时开始BFS
        int total = 0;
        List<Queue<int[]>> queueList = new ArrayList<>();
        List<int[]> startnodes = new ArrayList<>();    //当前队列起始点

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] > 1) {
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    queueList.add(queue);
                    startnodes.add(new int[]{i, j});
                }
            }
        }
        while (true) {
            for (int i = 0; i < queueList.size(); i++) {
                Queue<int[]> queue = queueList.get(i);
                int size = queue.size();
                int[] ints = startnodes.get(i);
                //将每个队列的当前的元素遍历一遍
                while (!queue.isEmpty() && grid[ints[0]][ints[1]] > 1 && size-- > 0) {
                    int[] peek = queue.remove();

                    int x = peek[0], y = peek[1];

                    if (grid[x][y] == 0) {
                        grid[x][y] = 1;
                        grid[ints[0]][ints[1]]--;
                        total += Math.abs(x - ints[0]) + Math.abs(y - ints[1]);
                    }

                    if (x > 0)
                        queue.add(new int[]{x - 1, y});
                    if (x < 2)
                        queue.add(new int[]{x + 1, y});
                    if (y > 0)
                        queue.add(new int[]{x, y - 1});
                    if (y < 2)
                        queue.add(new int[]{x, y + 1});
                }
            }
            //当startnodes全为1时结束
            int sum = 0;
            for (int[] startnode : startnodes) {
                sum += grid[startnode[0]][startnode[1]];
            }
            if (sum == startnodes.size())
                break;
        }
        return total;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{0, 2, 3}, {2, 0, 1}, {0, 1, 0}};
        int i = new Solution().minimumMoves(grid);
        System.out.println(i);
    }
}
